//请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有： 
//
// 
// get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1 
// add(value)：将价格为 value 的商品加入待结算商品队列的尾部 
// remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1 
// 
//
// 注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1) 
//
// 
//
// 示例 1： 
//
// 
//输入: 
//["Checkout","add","add","get_max","remove","get_max"]
//[[],[4],[7],[],[],[]]
//
//输出: [null,null,null,7,4,7]
// 
//
// 示例 2： 
//
// 
//输入: 
//["Checkout","remove","get_max"]
//[[],[],[]]
//
//输出: [null,-1,-1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= get_max, add, remove 的总操作数 <= 10000 
// 1 <= value <= 10^5 
// 
//
// 
//
// Related Topics 设计 队列 单调队列 👍 533 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ldltd
 * @date 2025-05-23 16:03:09
 * @description LCR 184.设计自助结算系统
 */
public class DuiLieDeZuiDaZhiLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 DuiLieDeZuiDaZhiLcof fun=new DuiLieDeZuiDaZhiLcof();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Checkout {
    Deque<Integer> q;
    Deque<Integer> max;

    public Checkout() {
        q = new ArrayDeque<>();
        max = new ArrayDeque<>();

    }

    public int get_max() {
        if(q.isEmpty()) return -1;
        return max.peekFirst();
    }
    // 1 6 5 4 3 2
    //
    public void add(int value) {
        q.offer(value);
        // 移除 maxDeque 尾部所有比 value 小的元素，保证队列单调递减
        //直到移除当前value，前面所有的队列中的值都比他小
        //
        while (!max.isEmpty() && value > max.peekLast()) {
            max.pollLast();
        }
        max.offerLast(value);
    }

    public int remove() {
        if (q.isEmpty()) return -1;
        int removed = q.poll();
        // 如果移除的元素是当前最大值，才从 maxDeque 中移除，max和q不一定大小一样
        if (removed == max.peekFirst()) {
            max.pollFirst();
        }
        return removed;
    }
}

/**
 * Your Checkout object will be instantiated and called as such:
 * Checkout obj = new Checkout();
 * int param_1 = obj.get_max();
 * obj.add(value);
 * int param_3 = obj.remove();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
